The invention relates generally to a method for routing data packets through a packet communication network and more specifically to a method for routing data packets in a network where some nodes can roam during network operation.
Packet communication is a form of data communication whereby segments or packets of data are routed with error checking and confirmation of receipt. Packets may be transmitted directly between a source and destination or relayed via relay stations. Several methods of data packet routing are known.
One method is known as directory-based routing. According to this method the address in the header of a packet is used as an index to a directory of packet routing lists stored in a transmitting or source node. A packet routing list consists of an ordered list of packet node identifiers or call signs that represent a transmission path from the transmitting node to the destination. Packet routing lists must be prepared with knowledge about the location of each node in the network. Directory-based routing schemes require continued maintenance and communication of network interconnection information employed in the directory. Each of these functions drains network resources and this can severely reduce performance in a large network. However, directory-based routing techniques have the advantage of permitting optimization of routing for a wide variety of network parameters, including data delay, throughput, reliability, priority and the like.
Another basic routing technique is the non-directory-based routing technique. In non-directory-based routing, the complexities associated with directory-based routing techniques are avoided. There is no need to store connectivity information for each transmitting node in the network thus reducing the amount of overhead processing that must be done by the network to preserve network connections. However, non-directory-based routing techniques generally do not permit network parameter optimization.
In U.S. Pat. No. 4,939,726, issued to Baran et al. and assigned to the assignee of the present invention, a non-directory-based routing method and system that permit network parameter optimization are disclosed. According to the method described therein, each stationary node in a network is uniquely identified by absolute geographical coordinates or by a code indicating absolute location in an external coordinate-based reference system (node coordinates), and such absolute geographical coordinates or the equivalent are employed as part of a packet identifier for each packet. A means at each node through which a packet is routed uses the packet destination coordinates and the node coordinates its neighboring nodes to determine a desired forwarding route of a data packet. The routing may be prioritized according to preselected criteria, preferably achieving optimum forward progress, that is, maximum forward progress using the least amount of power and taking into account characteristics of the system.
Accordingly, the disclosed packet routing method requires no routing directory or table to perform data routing. Each stationary node of the network collects or is otherwise provided with information about the quality of communication between itself and the nodes within the stationary node's communication range. When a data packet has been received at a node, the data packet is routed further through the network based on criteria derived from the history of communication between the local node and its neighbors. The criteria include distance, power requirements, retry history (reliability), throughput history, speed of transfer (net data rate), network delay, and data priority. Typically, there is an initialization procedure which is executed to determine the latitude and longitude of neighbors within a destination quadrant, and the criteria are weighted in accordance with preselected preferences to establish, at each subject node, a link quality (LQ) factor for each possible destination local to the subject node.
A packet in the Baran network is organized with four layers of header information as follows: EQU L1H L2H L3H L4H data L1T
where:
L indicates "layer"; PA1 H indicates "header"; PA1 T indicates "tailer."
The Layer 1 header is responsible for transferring data in a packet in error-free form and includes a checksum value for comparing accuracy of packet transmission.
The Layer 2 header comprises the local destination address, the local or circuit source address, a pro-type field (packet protocol and type) and a frame identification. The destination address is the geographic coordinates of the next local destination and the source address is the geographic coordinates of the local node. The destination address of a received packet becomes the source address of the same packet on its retransmission, and the destination address for retransmission is selected by the local node based on analysis of the metrics used to establish optimum forward progress. The Layer 2 local destination is not the ultimate destination of the packet. The ultimate destination address is contained in a Layer 3 header, which is used for routing a packet between any source and any destination within a wide area net or between wide area nets.
The Layer 3 header is examined upon receipt of a packet at any node to determine if the wide-area-network destination address (WANDA) in the header corresponds to the WANDA of the node. If the WANDAs are not identical, the node forwards the packet to a next hop in the network. Several routing protocols may be used.
The LAN Destination Address is the identifier of the exact device within the LAN. The LAN Source Address is the device identifier of the originating device. The LAN Source Address is used by the destination device for formatting a response packet. Routing a response back to the source merely involves swapping the LAN Destination Address for the LAN Source Address, assuming the Layer 3 header has been properly rebuilt for the return.
Each device in the network thus has a primary address, namely, the WAN Address, and a secondary address, namely, the LAN Address. The WAN address is the unique latitude and longitude designation of each repeater node, within one second (20 meters) of geographic accuracy. All devices within the LAN of the repeater node use the WAN Address of the repeater node as their WAN Address.
The coordinate-based addressing method described above provides a satisfactory solution to the problem of non-directory routing in a network consisting entirely of stationary nodes. However, many networks further comprise mobile or roaming nodes. Such nodes cannot be assigned the absolute geographic coordinates required by the geographical addressing method.
One method that has been employed in prior art networks designed for use with roaming nodes, such as cellular telephone systems, is for the stationary nodes in the system to continuously keep track of and in touch with each roaming node and to "hand off" roaming nodes from one stationary node to another. Such a system requires tremendous processing and communication overhead to take place within and between each stationary node and is contrary to the reduced processing desired in a non-directory-based system. Such an approach is particularly inefficient when a roaming node does not continuously transmit data, but instead transmits packets infrequently and at unpredictable times.
What is needed is a routing method that permits roaming nodes to be addressed in a network in which stationary nodes are addressed using a coordinate-based addressing method and that does not require excessive processing by the network or the stationary nodes in the network to maintain contact with the roaming nodes.